Just as the visited set helped us identify unreachable components, its primary role is to prevent the single most critical error in tree-building: forming a cycle. In algorithms like Prim's, it is inevitable that our priority queue will contain edges that connect two vertices already in the tree.

  • The visited set is our essential safeguard against forming cycles.
  • Before adding an edge (u, v) to our MST, we perform a crucial check: if v in visited.
  • If the destination vertex v is already in our set, adding the edge would create a redundant path and thus a cycle.
  • We simply discard this edge and move to the next cheapest one in our priority queue. This check guarantees the acyclic property of the final result.
Python: Cycle Prevention Check
1# Simulate a state in Prim's algorithm using the Shared_Graph
2# Let's say we have already added A, C, and B to our MST
3# The path is A-C-B
4
5mst_edges = [('A', 'C', 3), ('C', 'B', 1)]
6visited = {'A', 'C', 'B'}
7
8# Now, the algorithm considers the next-best edge from the priority queue.
9# Suppose this edge is (A, B) with weight 4, which was added
10# to the queue when we first visited A.
11
12next_edge_to_consider = ('A', 'B', 4)
13u, v, weight = next_edge_to_consider
14
15print(f"MST-in-progress: {mst_edges}")
16print(f"Visited vertices: {visited}")
17print(f"---")
18print(f"Considering edge: ({u}, {v}) with weight {weight}")
19
20# The crucial check to prevent forming a cycle
21if v in visited:
22  print(f"Result: REJECTED. Vertex '{v}' is already visited.")
23  print("Adding this edge would form the cycle A-C-B-A.")
24else:
25  # This code block is NOT executed
26  visited.add(v)
27  mst_edges.append((u, v, weight))
28  print("Result: Edge added.")
29
30print(f"---\nFinal MST remains: {mst_edges}")